package com.tgy.leetcode;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;

/**
 * @Author: tgy
 * @Date: 1/7/21 10:27 AM
 */
public class _547_省份数量_union_find {

    public int findCircleNum(int[][] isConnected) {

        if (isConnected == null || isConnected.length == 0 || isConnected[0].length == 0) {

            return 0;
        }

        int[] gather = new int[isConnected.length];
        for (int i = 1; i < gather.length; i++) {

            gather[i] = i;
        }


        for (int i = 0; i < isConnected.length; i++) {

            for (int j = 0; j < isConnected[i].length; j++) {

                if (isConnected[i][j] == 1) {

                    addGather(gather, i,j);
                }
            }
        }

        int count = 0;

        for (int i = 0; i < gather.length; i++) {

            if (gather[i] == i) {

                count++;
            }
        }

        return count;
    }

    private void addGather(int[] gather,int i, int j) {

        while (gather[i] != i) {

            i = gather[i];
        }


        while (gather[j] != j) {

            j = gather[j];
        }

        gather[j] = gather[i];
    }

}
